//相同的树
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (p == nullptr && q == nullptr)
            return true;
        if (p == nullptr || q == nullptr)
            return false;
        
        if (p->val != q->val)
            return false;

        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};

//翻转二叉树
class Solution {
public:
    void _invertTree(TreeNode* root)
    {
        if (root == nullptr)
            return;

        swap(root->left, root->right);

        _invertTree(root->left);
        _invertTree(root->right);
    }
    TreeNode* invertTree(TreeNode* root) {
        _invertTree(root);

        return root;
    }
};

//对称二叉树
class Solution {
public:
    // bool isSameTree(TreeNode* p, TreeNode* q) {
    //     if (p == nullptr && q == nullptr)
    //         return true;
    //     if (p == nullptr || q == nullptr)
    //         return false;
        
    //     if (p->val != q->val)
    //         return false;

    //     return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    // }

    // void _invertTree(TreeNode* root)
    // {
    //     if (root == nullptr)
    //         return;

    //     swap(root->left, root->right);

    //     _invertTree(root->left);
    //     _invertTree(root->right);
    // }
    // TreeNode* invertTree(TreeNode* root) {
    //     _invertTree(root);

    //     return root;
    // }
    // bool isSymmetric(TreeNode* root) {
    //     if (root == nullptr)
    //         return true;

    //     return isSameTree(root->left, invertTree(root->right));
    // }

    bool _isSymmetric(TreeNode* left, TreeNode* right)
    {
        if (left == nullptr && right == nullptr)
            return true;
        if (left == nullptr || right == nullptr)
            return false;

        if (left->val != right->val)
            return false;
        
        return _isSymmetric(left->left, right->right) && _isSymmetric(left->right, right->left);        
    }
    bool isSymmetric(TreeNode* root) {
        if (root == nullptr)
            return true;

        return _isSymmetric(root->left, root->right);
    }
};


//另一棵树的子树
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (p == nullptr && q == nullptr)
            return true;
        if (p == nullptr || q == nullptr)
            return false;
        
        if (p->val != q->val)
            return false;

        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }

    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        if (root == nullptr)
            return false;

        return isSameTree(root, subRoot) || isSubtree(root->left, subRoot) ||  isSubtree(root->right, subRoot);
    }
};